package shelly.freshman.class01;

import java.util.Arrays;

/**
 * @author: Shelly
 * @create: 2024-02-21 15:15:42
 * @version: 1.0
 * @describe: 选择排序 + 对数器
 * 解决方案：1、找到最小值，放在左侧；2、找到最大值，放最右侧
 * 提升点：【##】
 * 1、边界要卡准：空null，0，1，最大，最小，不要漏
 * 2、引用类型，内存地址
 * 3、程序员英语
 */
public class Code01_SelectionSort {
    /**
     * 选择排序
     * @param arr
     */
    public static void selectionSort(int[] arr){
        // 【##】1位的也不用比较
        //if (arr == null || arr.length == 0){
        if (arr == null || arr.length < 2){
            return;
        }

        // 【##】最后一位不要比较
        //for (int i = 0; i < arr.length; i++) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;// 已经放好位置的最小值可以不看了
            for (int j = i; j < arr.length; j++) {
                // 【##】简单的判断逻辑，三元运算的效率 > if
                /*if (arr[j] < arr[min]){
                    min = j;
                }*/
                min = arr[j] < arr[min] ? j : min;// 三元运算必有返回值
            }
            swap(arr,i,min);
        }

    }

    /**
     * 【校验组】系统自带的排序
     * @param arr
     */
    public static void AyyaysSort(int[] arr){
        Arrays.sort(arr);
    }

    /**
     * 数组数据交换
     * 【##】切记不能直接int交换，只有引用类型才能通过修改内存地址的值，来影响入参
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr,int i,int j){
        int s = arr[i];
        arr[i] = arr[j];
        arr[j] = s;
    }

    /**
     * 生成数组,数组非空
     * @param maxValue 最大值
     * @param maxLength 最大长度
     * @return
     */
    public static int[] generateRandomArray(int maxValue,int maxLength){
        // Math.random()   [0,1)
        // Math.random() * N  [0,N)
        // (int)(Math.random() * N)  [0, N-1]
        // [1,maxLength]
        int[] arr = new int[(int)((maxLength + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            // [-maxValue,maxValue]
            arr[i] = (int)((maxValue + 1) * Math.random()) - (int)(maxValue * Math.random());
        }
        return arr;
    }

    /**
     * 拷贝数组，指向不同的内存地址
     * @param arr
     * @return
     */
    public static int[] copyArray(int[] arr){
        // 【##】 注意边界
        if (arr == null){
            return null;
        }
        int[] arrCopy = new int[arr.length];
        for (int i = 0; i < arrCopy.length; i++) {
            arrCopy[i] = arr[i];
        }
        return arrCopy;
    }

    /**
     * 判断数组是否相等
     * @param arr1
     * @param arr2
     * @return
     */
    public static boolean isEqual(int[] arr1,int[] arr2){
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) return false;

        /*if (arr1 != null && arr2 != null && arr1.length != arr2.length){// 如果为空，会空指针报错
            return false;
        }*/
        if (arr1 == null && arr2 == null) return true;
        if (arr1.length != arr2.length) return false;

        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }

    /**
     * 打印数组
     * @param arr
     */
    public static void printArr(int[] arr){
        // 【##】为空的边界值要多注意
        if (arr == null){
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        // 判断数组是否相等:测试边界值
        System.out.println("=============="+isEqual(null,null)+"============");

        int testTime = 100000;// 测试次数
        int maxLength = 100;// 100 一开始不用太大，不方便测试，5就很好
        int maxValue = 100;
        System.out.println("开始=================");
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxLength,maxValue);
            int[] arr1 = copyArray(arr);
            int[] arr2 = copyArray(arr);
            selectionSort(arr1);
            AyyaysSort(arr2);
            if (!isEqual(arr1,arr2)){
                System.out.println("失败！错误数组：");
                printArr(arr);
                break;// 【##】不用把所有的错误数组都打印出来，留一个做测试即可，节省资源和时间
            }
        }
        System.out.println("结束=================");
    }

    /*public static void main2(String[] args) {
        int[] arr = generateRandomArray(2,2);

    }*/
}
